﻿// 0819train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <limits>

using namespace std;

/*
 有一个大小是N * M的战场地图，被墙壁'#' 分隔成大小不同的区域，
 上下左右四个方向相邻的空地 '.'，属于同一个区域，只有空地上可能存在敌人'E'，
 请求出地图上总共有多少区域里的敌人数小于K

输入描述
第一行输入为N M K;
N表示地图的行数，M表示地图的列数，K表示目标敌人数量
N, M <= 100
之后为一个N x M大小的字符数组

输出描述
敌人数小于K的区域数量

输入
3 5 2
..#EE
E.#E.
###..
输出
1
 */

class Solution01
{
public:
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
    int row_size, col_size;
    queue <pair<int, int>>bfs_queue;
    int target_count = 0;
    int result = 0;
    void solve01(vector<vector<char>>&grid, int limit)
    {
        //bfs_queue checked_grid DirectionGrid
        row_size = grid.size();
        col_size = grid[0].size();

        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked(row_size, checked_status);

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                int first_val = grid[r][c];
                bool is_first_visited = checked[r][c];
                if (first_val !='#' && !is_first_visited)
                {
                    bfs_queue.push(make_pair(r, c));
                    checked[r][c] = true;

                    //重置target_count
                    target_count = 0;
                    while (!bfs_queue.empty())
                    {
                        pair<int, int>top_node = bfs_queue.front();
                        bfs_queue.pop();

                        if (grid[top_node.first][top_node.second]=='E')
                        {
                            target_count++;
                        }

                        for (auto& dir_vec : DirectionGrid)
                        {
                            int curr_r = top_node.first + dir_vec[0];
                            int curr_c = top_node.second + dir_vec[1];

                            bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                            bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                            if (is_curr_r&&is_curr_c)
                            {
                                bool is_visited = checked[curr_r][curr_c];
                                int curr_val = grid[curr_r][curr_c];
                                bool is_available = curr_val != '#';

                                if (!is_visited && is_available)
                                {
                                    bfs_queue.push(make_pair(curr_r, curr_c));
                                    checked[curr_r][curr_c] = true;

                                }


                            }

                            //dir_vec------
                        }
                        //while (!bfs_queue.empty())
                    }
                    if (target_count<limit)
                    {
                        result += 1;
                    }

                }

                //for col
            }
            //for row
        }

        cout << result;
        //solve01------
    }
};


/*
 输入 m 和 n 两个数，m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据。
 棋盘中存在数字和"."两种字符，如果是数字表示该位置是一匹马，
 如果是"."表示该位置为空的，棋盘内的数字表示为该马能走的最大步数。
例如棋盘内某个位置一个数字为 k，表示该马只能移动 0~k 步的距离。
棋盘内的马移动类似于中国象棋中的马移动，先在水平或者垂直方向上移动一格，然后再将其移动到对角线位置。
棋盘内的马可以移动到同一个位置，同一个位置可以有多匹马。
请问能否将棋盘上所有的马移动到同一个位置，若可以请输出移动的最小步数。若不可以输出 0

输入描述
输入m 和 n 两个数，m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据。
输出描述
能否将棋盘上所有的马移动到同一个位置，若可以请输入移动的最小步数。若不可以输出 0。

示例1
输入
3 2
. .
2 .
. .
输出
0

示例2
输入
3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .
输出
17

 */
class Solution02
{
public:
    vector<vector<int>>DirectionGrid;
    int row_size, col_size;
    //可变区
    int curr_target = 0;
    int curr_step_limit = 0;
    
    //记录每一轮叠加的结果
    vector<vector<int>>statistic_grid;
    //bfs_queue DirectionGrid checked每一轮建新的
    vector<vector<int>>getDirectionGrid()
    {
        vector<vector<int>>simpleDir = { {-1,0},{1,0},{0,-1},{0,1} };
        vector<vector<int>>trangleDir = {{-1,-1},{-1,1},{1,-1},{1,1}};

        vector<vector<int>>totalDir;
        for (auto&num1:simpleDir)
        {
	        for (auto&num2:trangleDir)
	        {
                vector<int>new_dir(2);
                new_dir[0] = num1[0] + num2[0];
                new_dir[1] = num1[1] + num2[1];

                if (new_dir[0]!=0 && new_dir[1]!=0)
                {
                    totalDir.push_back(new_dir);
                }
                
	        }
        }
        return totalDir;
    }

    bool updateStatistic(vector<vector<int>>&checked)
    {
        bool result = false;
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                if (curr_target==1)
                {
                    if (checked[r][c] != -1)
                    {
                        statistic_grid[r][c] = checked[r][c];

                    }
                }
                else
                {
                    if (checked[r][c]==-1)
                    {
                        statistic_grid[r][c] = -1;
                    }
                    else
                    {
                        if (statistic_grid[r][c]!=-1)
                        {
                            result = true;
                            statistic_grid[r][c] += checked[r][c];
                        }

                    }

                }

            }

        }

        //cout << "checked" << endl;
        //for (auto& mini_vec : checked)
        //{
        //    for (auto& num : mini_vec)
        //    {
        //        cout << num << ' ';
        //    }
        //    cout << '\n';
        //}
        //cout << '\n';

        //cout << "statistic" << endl;
        //for (auto& mini_vec : statistic_grid)
        //{
        //    for (auto& num : mini_vec)
        //    {
        //        cout << num << ' ';
        //    }
        //    cout << '\n';
        //}
        //cout << '\n';

        return result;

    }

    bool IsNum(int oh_num)
    {
        return oh_num > 0;
    }

    void bfs(vector<vector<int>>&checked, queue<pair<int, int>>&bfs_queue)
    {
        int curr_step_count = 0;
        while (!bfs_queue.empty())
        {
            curr_step_count++;
            if (curr_step_count > curr_step_limit)
            {
                break;
            }

            int q_size = bfs_queue.size();

            for (int i=0; i<q_size; i++)
            {
                pair<int, int>top_node = bfs_queue.front();
                bfs_queue.pop();

                for (auto& dir_vec : DirectionGrid)
                {
                    int curr_r = top_node.first + dir_vec[0];
                    int curr_c = top_node.second + dir_vec[1];

                    bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                    bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                    if (is_curr_r && is_curr_c)
                    {
                        bool is_visited = checked[curr_r][curr_c] > -1;
                        if (!is_visited)
                        {
                            bfs_queue.push(make_pair(curr_r, curr_c));
                            checked[curr_r][curr_c] = curr_step_count;
                        }

                    }

                }
            }

            //while(!bfs_queue.empty())
        }
	    
    }

    void solve02(vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();
        DirectionGrid = getDirectionGrid();
        vector<vector<int>>s_grid(row_size, vector<int>(col_size,-1));
        statistic_grid = s_grid;


        for (int r=0; r<row_size;r++)
        {
            for (int c=0; c<col_size; c++)
            {
                vector<int>checked_step(col_size, -1);
                vector<vector<int>>checked(row_size, checked_step);

                int first_val = grid[r][c];
                if (IsNum(first_val))
                {
                    queue<pair<int, int>>bfs_queue;
                    bfs_queue.push(make_pair(r, c));
                    checked[r][c] = 0;
                    //更新目前找到马的数量
                    curr_target += 1;
                    curr_step_limit = first_val;

                    //if (r==8 && c==6)
                    //{
                    //    cout << grid[r][c] << endl;
                    //}
                    //cout << r << ' ' << c << endl;
                    bfs(checked, bfs_queue);

                    bool is_meet = updateStatistic(checked);
                    if (curr_target>1 &&!is_meet)
                    {
                        //cout << r << ' ' << c << endl;

                        //for (auto& mini_vec : statistic_grid)
                        //{
                        //    for (auto& num : mini_vec)
                        //    {
                        //        cout << num << ' ';
                        //    }
                        //    cout << '\n';
                        //}
                        cout << 0;
                        return;
                    }

                }
                //for col------
            }
            //for row------
        }

        if (curr_target==1)
        {
            cout << 0;
            return;
        }

        int result = INT_MAX;
        for (auto&mini_vec:statistic_grid)
        {
	        for (auto&num:mini_vec)
	        {
                if (num!=-1)
                {
                    result = min(result, num);
                }
                //cout << num << ' ';
	        }
            //cout << '\n';
        }
        cout << result;

    }

};

int main()
{
	{
/*
3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .
*/
/*
0 0

 */
        //string str1 = "4 7 . 4 8";
        //string str2 = "4 7 4 4 .";
        //string str3 = "7 . . . .";
        //vector<string>str_vec = { str1,str2,str3 };
        //vector<vector<int>>grid;
        //for (auto&oh_str:str_vec)
        //{
        //    vector<int>char_vec;
        //    stringstream oh_sstream(oh_str);
        //    string token;
        //    while (oh_sstream >>token)
        //    {
        //        if (token==".")
        //        {
        //            char_vec.push_back(-1);
        //        }
        //        else
        //        {
        //            char_vec.push_back(stoi(token));
        //        }
        //    }
        //    grid.push_back(char_vec);
        //}
        int row_size, col_size;
        cin >> row_size >> col_size;
        cin.ignore();
        vector<vector<int>>grid(row_size,vector<int>(col_size));

        vector<vector<string>>str_grid;
        string input;
        for (int i=0; i<row_size; i++)
        {
            vector<string>mini_vec;
            getline(cin, input);
            stringstream oh_sstream(input);
            string token;
            while (oh_sstream>>token)
            {
                mini_vec.push_back(token);
            }
            str_grid.push_back(mini_vec);
        }

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                if (str_grid[r][c] == ".")
                {
                    grid[r][c] = -1;
                }
                else
                {
                    grid[r][c] = stoi(str_grid[r][c]);
                }
	        }
        }

        //for (auto&min_vec: grid)
        //{
        //    for (auto&oh_num:min_vec)
        //    {
        //        cout << oh_num << ' ';
        //    }
        //    cout << '\n';
        //}

        Solution02 solu;
        solu.solve02(grid);
        //vector<vector<int>>dir_grid = solu.getDirectionGrid();

        //for (auto&min_vec:dir_grid)
        //{
        //    for (auto&num:min_vec)
        //    {
        //        cout << num << ' ';
        //    }
        //    cout << '\n';
        //}


        return 0;
	}

/*
3 5 2
..#EE
E.#E.
###..
 */
    //string str1 = "..#EE";
    //string str2 = "E.#E.";
    //string str3 = "###..";
    //vector<string>str_vec = { str1,str2,str3 };
    //int limit = 2;
    int row_size, col_size, limit;
    cin >> row_size >> col_size >> limit;

    vector<vector<char>>grid(row_size,vector<char>(col_size));
    for (int r=0; r<row_size; r++)
    {
        for (int c=0; c<col_size; c++)
        {
            cin >> grid[r][c];
        }

    }

    //for (auto&oh_str:str_vec)
    //{
    //    vector<char>char_vec;
    //    for (auto&oh_char:oh_str)
    //    {
    //        char_vec.push_back(oh_char);

    //    }
    //    grid.push_back(char_vec);
    //}

    Solution01 solu;
    solu.solve01(grid, limit);
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
